#include <bits/stdc++.h>
#include "../../tools/tools.h"
using namespace std;

constexpr int INF = 0x7fffffff; // 无穷大
typedef long long ll;

class Solution {
public:
    long long maximumTotalDamage(vector<int>& power) {
        unordered_map<int, int> cnt;
        vector<long long> data;
        for (auto& p : power) {
            cnt[p]++;
            if (cnt[p] == 1) data.push_back(p);
        }
        ranges::sort(data);
        const int n = data.size();

        vector dp(n, vector(2, 0LL));
        dp[0][1] = data[0] * cnt[data[0]];
        for (int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i - 1][1] , dp[i - 1][0]);
            int j = i - 1;
            while (j >= 0 && (data[j] == data[i] - 1 || data[j] == data[i] - 2)) {
                j--;
            }
            dp[i][1] = data[i] * cnt[data[i]] + (j >= 0 ? max(dp[j][1], dp[j][0]) : 0);
        }
        return max(dp[n - 1][0], dp[n - 1][1]);
    }
};

int main(int argc, char* argv[]) {
    Solution s;
    // 2 2 3 5 7 8 9 9 10 10

    // 2 4 3 9 11 17 18 27 21 31
    vector data = {5, 9, 2, 10, 2, 7, 10, 9, 3, 8}; //31
    s.maximumTotalDamage(data);
}
